package com.major.dawn.leetCode.array;

import java.util.HashMap;
import java.util.Set;
import java.util.TreeSet;

public class ThirdMaxNum {

//    查看了高票题解的第二种方法，基本和我的时间复杂度是一样的，第一种写法红黑树实现不太懂呀，树形的数据结构真的很重要
    public int thirdMax(int[] nums) {

        int length = nums.length;
        if (length == 0) {
            return 0;
        }

        HashMap<Integer, Integer> integerHashMap = new HashMap<>(length);
        for (int i = 0; i < length; i++) {
            integerHashMap.put(nums[i], 1);
        }
        Set<Integer> integers = integerHashMap.keySet();
        int size = integers.size();
        Integer[] toArray = integers.toArray(new Integer[size]);

        if (size == 1) {
            return toArray[0];
        }

        if (size == 2) {

            if (toArray[0] > toArray[1]) {
                return toArray[0];
            } else {
                return toArray[1];
            }
        }

        for (int i = 0; i < 3; i++) {
            int curNum = toArray[i];
            int maxIndex = i;
            for (int j = i + 1; j < size; j++) {
                if (toArray[j] > curNum) {
                    curNum = toArray[j];
                    maxIndex = j;
                }
            }

            swap(toArray, i, maxIndex);
        }

        return toArray[2];
    }

    private void swap(Integer[] nums, int i, int maxIndex) {
        if (i == maxIndex) {
            return;
        }
        int tem = nums[i];
        nums[i] = nums[maxIndex];
        nums[maxIndex] = tem;
    }

    public int thirdMaxTree(int[] nums) {
        if (nums == null || nums.length == 0) throw new RuntimeException("error");

        TreeSet<Integer> set = new TreeSet<>();
        for (Integer elem : nums) {
            set.add(elem);
            if (set.size() > 3) set.remove(set.first());
        }

        return set.size() < 3 ? set.last() : set.first();   // set.last() 里面最大的元素
    }



    public static void main(String[] args) {
        ThirdMaxNum thirdMaxNum = new ThirdMaxNum();
        int thirdMax = thirdMaxNum.thirdMax(new int[]{2, 2, 3, 1});
        System.out.println(thirdMax);

    }
}
